package algorithm.sort.review2;

import java.util.Arrays;

public class Radix {
    public static void main(String[] args) {
        int[] arr = {3, 3, 4, 1, 3, 56, 242, 1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 基数排序复习
     *
     * @param arr
     */
    public static void sort(int[] arr) {
        //找最大的数
        //计算需要循环多少轮
        //循环
        //将数组中的数放到桶中
        //将桶中的数依次取出

        int[][] bucket = new int[10][arr.length];
        int[] bucketCount = new int[10];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        int repeatCount = String.valueOf(max).length();
        int base;
        int m;
        for (int i = 0, n = 1; i < repeatCount; i++, n *= 10) {
            //放到桶中
            for (int j = 0; j < arr.length; j++) {
                base = arr[j] / n % 10;
                bucket[base][bucketCount[base]++] = arr[j];
            }
            //从桶中取出
            m = 0;
            for (int j = 0; j < bucket.length; j++) {
                for (int k = 0; k < bucketCount[j]; k++) {
                    arr[m++] = bucket[j][k];
                }
                bucketCount[j] = 0;
            }
        }
    }
}
